#include<iostream>
#include<cstring>
using namespace std;
const int maxn=1000;
int n,m;
int dis[maxn][maxn],may[maxn],ans[maxn],mindis[maxn];
long long minans=11111111111;
int inf=10000000;
int cal(int x)
{
    int sum=0;
    for(int i=x;i<=n;i++)
    sum+=mindis[may[i]];
    return sum;
}
void dfs(int now,int sum)
{
    if(now==n)
    {
        if(sum+dis[may[now]][1]+dis[may[now]][may[now-1]]<minans)
        {
            for(int i=1;i<=n;i++)
            ans[i]=may[i];
            minans=sum+dis[may[now]][1]+dis[may[now]][may[now-1]];
        }
        return;
    } 
    int re=cal(now);
    if(re+sum>=minans) 
    {cout<<"cut here: deep="<<now<<" ";return;}
    for(int i=now;i<=n;i++)
    {
        if(dis[may[now-1]][may[i]]!=inf&&sum+dis[may[now-1]][may[i]]<minans)
        {
            swap(may[i],may[now]);
            dfs(now+1,sum+dis[may[now-1]][may[now]]);
            swap(may[i],may[now]);
        }
    }
}
int main()
{
    cin>>n>>m;
    int x,y,z;
    // memset(dis,0x2f,sizeof(dis));
    // memset(mindis,0x2f,sizeof(mindis));
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        dis[i][j]=dis[j][i]=inf;
        mindis[i]=inf;
    }
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y>>z;
        dis[x][y]=dis[y][x]=z;
        mindis[x]=min(mindis[x],z);
        mindis[y]=min(mindis[y],z);        
    }
    for(int i=1;i<=n;i++)
    may[i]=i;
    dfs(2,0);
    cout<<endl;
    cout<<"shortest distance:"<<minans<<endl;
    cout<<"shortest way:";
    for(int i=1;i<=n;i++)
    cout<<ans[i]<<" ";
    cout<<1;
}





// #include<iostream>
// #include<cstring>
// using namespace std;
// const int maxn=30;
// int n,m;
// int dis[maxn][maxn],may[maxn],ans[maxn],mindis[maxn];
// long long minans=1111111111;
// int inf=100000;
// int cal(int x)
// {
//     int sum=0;
//     for(int i=x;i<=n;i++)
//     sum+=mindis[may[i]];
//     return sum;
// }
// void dfs(int now,int sum)
// {
//     if(now==n)
//     {
//         if(sum+dis[may[now]][1]+dis[may[now-1]][may[now]]<minans)
//         minans=sum+dis[may[now]][1]+dis[may[now-1]][may[now]];
//         return;
//     } 
//     int re=cal(now);
//     if(re+sum>=minans) 
//     return;
//     for(int i=now;i<=n;i++)
//     {
//         if(sum+dis[may[now-1]][may[i]]<minans)
//         {
//             swap(may[i],may[now]);
//             dfs(now+1,sum+dis[may[now-1]][may[now]]);
//             swap(may[i],may[now]);
//         }
//     }
// }
// int main()
// {
//     cin>>n;
//     for(int i=1;i<=n;i++)
//     mindis[i]=inf;
//     for(int i=1;i<=n;i++)
//     {
//         for(int j=1;j<=n;j++)
//         {
//             cin>>dis[i][j];
//             if(i!=j)
//             mindis[i]=min(mindis[i],dis[i][j]);
//         }
//     }
//     for(int i=1;i<=n;i++)
//     may[i]=i;
//     dfs(2,0);
//     cout<<minans<<endl;
//     return 0;
// }

